Cosa stiamo costruendo 🎯
- La struttura dati: Una Coda di priorità (CP).
- È un tipo di dato astratto come una lista o una coda, ma con una caratteristica particolare.
- Ogni elemento ha una "priorità" (un valore chiave).
- Quando esegui il comando "pop", ottieni sempre l'elemento con la priorità più altaottenuto l'elemento con la priorità più alta.
- Le operazioni:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- L'implementazione:Useremo un Heap binario massimo.
- Perché un heap? È efficiente! Un heap ci garantisce:
push: O(log N)pop: O(log N)peek: O(1)
Cos'è un heap massimo?
Un albero binario con due regole semplici:
1. Proprietà della forma
È un albero binario completo. Tutti i livelli sono pieni, tranne forse l'ultimo, che viene riempito da sinistra verso destra. Non ci sono vuoti.
Clicca una foglia per rimuoverla
2. Proprietà dell'heap massimo
La chiave di un genitore è maggiore o uguale aquelle dei figli. Questo garantisce che l'elemento più grandesia sempre nella radice.
Memorizzazione dell'albero 💾
Poiché l'albero è completo, possiamo memorizzarlo perfettamente in un semplice array.
Matematica degli indici (basata su 0)
Per un nodo all'indice i:
- Genitore
(i - 1) // 2 - Figlio sinistro
2 * i + 1 - Figlio destro
2 * i + 2
Consiglio:Memorizza queste formule! Sono la chiave per navigare nell'"albero" dentro il tuo array.